package com.gegewa.topic.sort;

import org.apache.commons.collections.CollectionUtils;
import org.junit.Test;

import java.util.*;

public class Sort {

    @Test
    public void test() {
//        sort1(listStudent());
//        sort2();
//        sort3();
//        sort4();
//        sort5();
//        sort6();
//        sort7();
//        sort8();
//        bubbleSort();
//        bubbleSortObject();
        int[] ints = listInteger();
//        quickSortBoth2(ints, 0, 3);
//        print(ints);
//        bucketSort(ints, 0, 100);
//        List<Student> studentList = Collections.emptyList();
//        List<Student> sList = listStudent();
//        studentList.addAll(sList);
//        print(studentList);
    }

    private <T extends Comparable> void sort1(List<T> list) {
        Collections.sort(list, new Comparator<T>() {
            @Override
            public int compare(T t1, T t2) {
                return t1.compareTo(t2);
            }
        });
        print(list);
    }

    private void sort2() {
        List<Student> studentList = listStudent();
        Collections.sort(studentList);
        print(studentList);
    }

    private void sort3() {
        List<Student> studentList = listStudent();
        studentList.sort(Comparator.comparing(Student::getName));
        print(studentList);
    }

    private void sort4() {
        List<Student> studentList = listStudent();
        Collections.sort(studentList, Comparator.comparing(Student::getAge));
        print(studentList);
    }

    private void sort5() {
        List<Student> studentList = listStudent();
        studentList.sort((s1, s2) -> s1.getAge() - s2.getAge());
        print(studentList);
    }

    private void sort6() {
        List<Student> studentList = listStudent();
        studentList.sort((Student s1, Student s2) -> s1.getAge() - s2.getAge());
        print(studentList);
    }


    private void sort7() {
        Integer[] integers = new Integer[4];
        integers[0] = 22;
        integers[1] = 55;
        integers[2] = 11;
        integers[3] = 33;

        Arrays.sort(integers, new Comparator<Integer>() {
            @Override
            public int compare(Integer t1, Integer t2) {
                return t1 - t2;
            }
        });
        print(integers);
    }

    private void sort8() {
        int[] integers = listInteger();

        Arrays.sort(integers);
        print(integers);
    }


    private void bubbleSort() {
        int[] integers = listInteger();
        for (int i = 0; i < integers.length - 1; i++) {
            for (int j = i + 1; j < integers.length; j++) {
                if (integers[i] > integers[j]) {
                    int t = integers[i];
                    integers[i] = integers[j];
                    integers[j] = t;
                }
            }
        }
        print(integers);
    }

    private void bubbleSortObject() {
        List<Student> studentList = listStudent();
        for (int i = 0; i < studentList.size() - 1; i++) {
            for (int j = i + 1; j < studentList.size(); j++) {
                if (studentList.get(i).getAge() > studentList.get(j).getAge()) {
                    Student t = studentList.get(i);
                    studentList.add(i, studentList.get(j));
                    studentList.remove(i + 1);
                    studentList.add(j, t);
                    studentList.remove(j + 1);
                }
            }
        }
        print(studentList);
    }

    private void quickSort(int[] integers, int start, int end) {
        if (start >= end) {
            return;
        }
        int base = integers[start];
        int i = start;
        int j = end;
        for (; j > i; j--) {
            if (integers[j] < base) {
                integers[i] = integers[j];
                i++;
                for (; i < j; i++) {
                    if (integers[i] > base) {
                        integers[j] = integers[i];
                        break;
                    }
                }
            }
        }
        integers[i] = base;
        quickSort(integers, start, i - 1);
        quickSort(integers, i + 1, end);
    }

    private void quickSortBoth(int[] integers, int start, int end) {
        if (start >= end) {
            return;
        }
        int base = integers[start];
        int i = start;
        int j = end;
        for (; j > i; j--) {
            if (integers[j] < base) {
                for (; i < j; i++) {
                    if (integers[i] > base) {
                        int t = integers[j];
                        integers[j] = integers[i];
                        integers[i] = t;
                        i++;
                        break;
                    }
                }
            }
        }
        integers[i] = base;
        quickSort(integers, start, i - 1);
        quickSort(integers, i + 1, end);
    }

    private void quickSortBoth2(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left, j = right, temp;
        while (i != j) {
            while (data[j] >= data[left] && i < j) {
                j--;
            }
            while (data[i] <= data[left] && i < j) {
                i++;
            }
            if (i < j) {
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        temp = data[left];
        data[left] = data[i];
        data[i] = temp;

        quickSortBoth2(data, left, i - 1);
        quickSortBoth2(data, i + 1, right);
    }

    private void bucketSort(int[] data, int start, int end) {
        int[] bucket = new int[end - start + 1];
        int offset = 0 - start;
        for (int d : data) {
            bucket[d + offset] = bucket[d + offset] + 1;
        }
        for (int i = 0; i < bucket.length; i++) {
            for (int j = 0; j < bucket[i]; j++) {
                System.out.println(i);
            }
        }

    }

    //将有二个有序数列a[first...mid]和a[mid...last]合并。
    void mergearray(int a[], int first, int mid, int last, int temp[])
    {
        int i = first, j = mid + 1;
        int m = mid,   n = last;
        int k = 0;

        while (i <= m && j <= n)
        {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }

        while (i <= m)
            temp[k++] = a[i++];

        while (j <= n)
            temp[k++] = a[j++];

        for (i = 0; i < k; i++)
            a[first + i] = temp[i];
    }
    void mergesort(int a[], int first, int last, int temp[])
    {
        if (first < last)
        {
            int mid = (first + last) / 2;
            mergesort(a, first, mid, temp);    //左边有序
            mergesort(a, mid + 1, last, temp); //右边有序
            mergearray(a, first, mid, last, temp); //再将二个有序数列合并
        }
    }

//    bool MergeSort(int a[], int n)
//    {
//        mergesort(a, 0, n - 1, p);
//    }

    private List<Student> listStudent() {
        List<Student> studentList = new ArrayList<>();
        Student s1 = new Student("Link", 22);
        Student s2 = new Student("Jane", 55);
        Student s3 = new Student("Kim", 11);
        Student s4 = new Student("Mei", 33);
        studentList.add(s1);
        studentList.add(s2);
        studentList.add(s3);
        studentList.add(s4);
        return studentList;
    }

    private int[] listInteger() {
        int[] integers = new int[4];
        integers[0] = 22;
        integers[1] = 55;
        integers[2] = 11;
        integers[3] = 33;
        return integers;
    }

    private void print(List list) {
        System.out.println("-----------");
        System.out.println(list);
    }

    private void print(Object[] objects) {
        System.out.println("-----------");
        for (Object obj : objects) {
            System.out.print(obj);
            System.out.print("    ");
        }
        System.out.println();
    }

    private void print(int[] objects) {
        System.out.println("-----------");
        for (Object obj : objects) {
            System.out.print(obj);
            System.out.print("    ");
        }
        System.out.println();
    }


}
